package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

import java.util.HashSet;

/**
 * 160. Intersection of Two Linked Lists
 *
 * Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect.
 * If the two linked lists have no intersection at all, return null.
 *
 * For example, the following two linked lists begin to intersect at node c1:
 *      [a1,a2] -+
 *               +-> [c1,c2,c3]
 *   [b1,b2,b3] -+
 * The test cases are generated such that there are no cycles anywhere in the entire linked structure.
 *
 * Note that the linked lists must retain their original structure after the function returns.
 *
 * Custom Judge:
 *   The inputs to the judge are given as follows (your program is not given these inputs):
 *     intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
 *     listA - The first linked list.
 *     listB - The second linked list.
 *     skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
 *     skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.
 *     The judge will then create the linked structure based on these inputs and pass the two heads,
 *     headA and headB to your program.
 *     If you correctly return the intersected node, then your solution will be accepted.
 *
 * Example 1:
 *   A     [4,1] -+
 *                +-> [8,4,5]
 *   B   [5,6,1] -+
 *  Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
 *  Output: Intersected at '8'
 *  Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
 *               From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5].
 *               There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
 *               - Note that the intersected node's value is not 1 because the nodes with value 1 in A and B
 *               (2nd node in A and 3rd node in B) are different node references.
 *               In other words, they point to two different locations in memory,
 *               while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point
 *               to the same location in memory.
 *
 * Example 2:
 *   A   [1,9,1] -+
 *                +-> [2,4]
 *   B       [3] -+
 *  Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
 *  Output: Intersected at '2'
 *  Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
 *               From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4].
 *               There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
 *
 * Example 3:
 *   A   [2,6,4] -+
 *                +-> []
 *   B     [1,5] -+
 *  Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
 *  Output: No intersection
 *  Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5].
 *               Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
 *               Explanation: The two lists do not intersect, so return null.
 *
 * Constraints:
 *  The number of nodes of listA is in the m.
 *  The number of nodes of listB is in the n.
 *  1 <= m, n <= 3 * 10^4
 *  1 <= Node.val <= 10^5
 *  0 <= skipA < m
 *  0 <= skipB < n
 *  intersectVal is 0 if listA and listB do not intersect.
 *  intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.
 *
 * Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?
 */
public class Num_0160 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode getIntersectionNode(ListNode headA, ListNode headB);

        default void assertExpected(int[] headA, int[] headB, int[] expected) {
            ListNode common = build(expected);
            ListNode newHeadA = concat(build(headA), common); // 评测系统中相交部分共用内存
            ListNode newHeadB = concat(build(headB), common);
            if (!assertEquals(getIntersectionNode(newHeadA, newHeadB), build(expected))) {
                getIntersectionNode(newHeadA, newHeadB);
            }
        }
    }

    private static class MyHashSetSolution implements Solution {

        @Override
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 其次：哈希集合找重复值：时O(m+n) 空O(n)
            /*
             * 相交链表，相交部分共用同一内存节点（即：引用相等处）
             */
            HashSet<ListNode> set = new HashSet<>();
            ListNode curA = headA;
            while (curA != null) {
                set.add(curA);
                curA = curA.next;
            }
            ListNode curB = headB;
            while (curB != null) { // 依次遍历找到引用第一个相等处即是
                if (set.contains(curB)) {
                    return curB;
                }
                curB = curB.next;
            }
            return null;
        }
    }

    private static class MyDoublePointerSolution implements Solution {

        @Override
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 最优：双指针对齐后二次遍历：时O(m+n) 空O(1)
            /*
             * 相交链表，相交部分共用同一内存节点（即：引用相等处）（不能反转链表，破坏了链表原始结构）
             *
             * 遍历长度，对齐开头，从对齐后的起点开始判断是否相等
             *    [1,2,3] -+
             *         ↑   +-> [8,4,6]
             *        [9] -+
             *         ↑
             */
            // 1.同时向后遍历
            ListNode curA = headA;
            ListNode curB = headB;
            while (curA != null && curB != null) {
                curA = curA.next;
                curB = curB.next;
            }
            // 2.对齐起始遍历点
            ListNode newCurA = headA; // 默认 A长==B长
            ListNode newCurB = headB;
            if (curA != null) { // A 长，A 跳过开头多出的个数
                while (curA != null) {
                    newCurA = newCurA.next;
                    curA = curA.next;
                }
            } else if (curB != null) { // B 长，B 跳过开头多出的个数
                while (curB != null) {
                    newCurB = newCurB.next;
                    curB = curB.next;
                }
            }
            // 3.再次遍历找相等点
            while (newCurA != null) {
                if (newCurA == newCurB) {
                    return newCurA;
                }
                newCurA = newCurA.next;
                newCurB = newCurB.next;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyDoublePointerSolution();
        solution.assertExpected(new int[]{4,1}, new int[]{5,6,1}, new int[]{8,4,5});
        solution.assertExpected(new int[]{1,9,1}, new int[]{3}, new int[]{2,4});
        solution.assertExpected(new int[]{2,6,4}, new int[]{1,5}, new int[]{});
    }
}
